// 链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。
// 指向另一 个节点的引用叫做链


(function () {
    function Node(element) {
        this.element = element;
        this.next = null;
    }

    function LinkedList() {
        this.head = new Node("head");
        this.find = find;
        this.insert = insert;
        this.remove = remove;
        this.display = display;
        this.findPrevious = findPrevious;
    }

    function find(item) {
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }

    function insert(newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        current.next = newNode;
    }

    function display() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            print(currNode.next.element);
            currNode = currNode.next;
        }
    }

    function findPrevious(item) {
        var currNode = this.head;
        while (!(currNode.next == null) &&
        (currNode.next.element != item)) {
            currNode = currNode.next;
        }
        return currNode;
    }

    function remove(item) {
        var prevNode = this.findPrevious(item);
        if (!(prevNode.next == null)) {
            prevNode.next = prevNode.next.next;
        }
    }


    // 主程序
    var cities = new LinkedList();
    cities.insert("Conway", "head");
    cities.insert("Russellville", "Conway");
    cities.insert("Carlisle", "Russellville");
    cities.insert("Alma", "Carlisle");
    cities.display();
    cities.remove("Carlisle");
    cities.display();
}());

function print(x) {
    x = x?x:"";
    console.log(x);
}
//-------------双向链表--------------------------------------------
// 尽管从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历则没那么简单。
// 通过 给 Node 对象增加一个属性,该属性存储指向前驱节点的链接,这样就容易多了。
// 此时向链 表插入一个节点需要更多的工作,我们需要指出该节点正确的前驱和后继。
// 但是在从链表 中删除节点时,效率提高了,不需要再查找待删除节点的前驱节点了。

(function () {
    function Node(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }

    function insert(newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next = newNode;
    }

    function remove(item) {
        var currNode = this.find(item);
        if (!(currNode.next == null)) {
            if( currNode.previous ){
                currNode.previous.next = currNode.next;
            }
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    }

    function findLast() {
        var currNode = this.head;
        while (currNode.next != null) {
            currNode = currNode.next;
        }
        return currNode;
    }

    function dispReverse() {
        var currNode = this.head;
        currNode = this.findLast();
        while (!(currNode.previous == null)) {
            print(currNode.element);
            currNode = currNode.previous;
        }
    }

    function display() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            print(currNode.next.element);
            currNode = currNode.next;
        }
    }

    function find(item) {
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }

    function LList() {
        this.head = new Node("head");
        this.find = find;
        this.insert = insert;
        this.display = display;
        this.remove = remove;
        this.findLast = findLast;
        this.dispReverse = dispReverse;
    }

    print("=========");
    var cities = new LList();
    cities.insert("Conway", "head");
    cities.insert("Russellville", "Conway");
    cities.insert("Carlisle", "Russellville");
    cities.insert("Alma", "Carlisle");
    cities.display();
    print();
    cities.remove("Carlisle");
    cities.display();
    print();
    cities.dispReverse();
}());